package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description
 * @date 2025/4/27 12:50
 */
public class TrimBST_669 {

    /**
     * dmsxl
     */
    public TreeNode trimBST2(TreeNode root, int low, int high) {
        if (root == null) return null;

        // 根
        // 当前节点小于low，其左一定<low，但是右不一定，所以还要判断右；右孩子 > low，但可能 < high，所以继续做递归修剪
        if (root.val < low) {
            return trimBST2(root.right, low, high);
        }
        // 同理，左孩子可能 < high
        if (root.val > high) {
            return trimBST2(root.left, low, high);
        }

        // 左
        root.left = trimBST2(root.left, low, high);

        // 右
        root.right = trimBST2(root.right, low, high);

        return root;
    }

    /**
     * 个人：错误解法
     */
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;

        // 找到待删除节点
        // 当前节点小于low，其左一定<low，但是右不一定，所以还要判断右
        if (root.val < low) {
            TreeNode left = root.left, right = root.right;

            if (left == null && right == null) {
                return null;
            } else if (left != null && right == null) {
                return null;
            } else {
                if ((right.val < low)) {
                    return null;
                } else {

                    return trimBST(right, low, high);
                }
            }
        } else if (root.val > high) {
            TreeNode left = root.left, right = root.right;

            if (left == null && right == null) {
                return null;
            } else if (left == null && right != null) {
                return null;
            } else {
                if ((left.val < low)) {
                    return null;
                } else {
                    return trimBST(left, low, high);
                }
            }
        }

        root.left = trimBST(root.left, low, high);

        root.right = trimBST(root.right, low, high);

        return root;
    }

}
